#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 5e4 + 5;

int n, m, k;
int a[N], pos[N];
int cnt[N];
ll tot, ans[N];
int l = 1, r;
void init() {
  int k = sqrt(n);
  rep(i, 1, n) pos[i] = (i - 1) / k + 1;
}
void add(int x) {
  cnt[x]++;
  tot += 2 * cnt[x] - 1;
}
void del(int x) {
  cnt[x]--;
  tot -= 2 * cnt[x] + 1;
}
struct Query {
  int l, r, id;
  bool operator<(Query x) const {
    if (pos[l] != pos[x.l]) return l < x.l;
    if (pos[l] & 1)
      return r < x.r;
    else
      return r > x.r;
  }
} q[N];
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> k;
  rep(i, 1, n) cin >> a[i];
  init();
  rep(i, 1, m) {
    cin >> q[i].l >> q[i].r;
    q[i].id = i;
  }
  sort(q + 1, q + m + 1);
  rep(i, 1, m) {
    while (r < q[i].r) add(a[++r]);
    while (r > q[i].r) del(a[r--]);
    while (l > q[i].l) add(a[--l]);
    while (l < q[i].l) del(a[l++]);
    ans[q[i].id] = tot;
  }
  rep(i, 1, m) cout << ans[i] << endl;
  return 0;
}